1. Field of the Invention
The present invention relates to a memory management system for a computer, and more particularly, to a paging system which resolves a page fault as soon as the critical data line which caused the page fault is received, without waiting for the rest of the page to be written into local memory.
2. Description of the Prior Art
As well known to those skilled in the art, microprocessors have local memory which stores the data needed by processes operating on the microprocessor. The local memory may be an on-board cache or the local (main) memory of the microprocessor. The main memory also may be cached to improve performance. Typically, the local memory operates in accordance with a paging system whereby one or more pages of memory are stored locally to the microprocessor for rapid access. In such paging systems, if the data requested by the microprocessor cannot be found in the page or pages currently stored in local memory, a page fault is issued, and the page containing the requested data is written into the local memory from an external, relatively slow secondary memory using known page replacement techniques. During this page writing (I/O transfer), the process requesting the data is stalled by the microprocessor until the entire page containing the requested data is written into local memory. The period during which the process is stalled is generally known as the storage latency.
Access to data in the secondary memory is typically much slower than access to data in local memory since the storage latency includes the I/O data transfer latency as well as the search time for finding the desired data in the secondary memory. Because of the relatively large search time for the secondary memory, the I/O data transfer latency is a relatively small percentage of the storage latency. For example, in a typical memory transfer from a disk, it may take 20 ms to find the requested page on the disk but only 2 ms to transfer the requested page (assuming a 4 kB page at 2 MB/sec) once it has been found. As a result, prior art efforts to reduce storage latency have concentrated on reducing the amount of time needed to find the page in the secondary storage devices. However, as the cost of random access memory (RAM) falls, RAMs are being used more frequently as the secondary storage devices. As known by those skilled in the art, RAMs have a relatively small access time, and as a result, in such systems the I/O data transfer latency has become a larger portion of the storage latency. Accordingly, it is desirable that this I/O data transfer latency be further reduced to minimize the storage latency so as to provide for the most efficient resolution of page faults.
I/O data transfer latency is often addressed by choosing a particular page size. The choice of page size is a complicated one and is based on the expected use of the machine, the expected size of main memory, and various constraints upon the hardware design such as the microprocessor's size and number of connections. In general, a larger page size reduces the size and complexity of the microprocessor and the virtual memory software. If the main memory of the system is large enough, the larger page size can also reduce the number of page faults necessary to load a process from secondary memory by increasing the amount of data retrieved on each fault. However, if main memory is not large enough to hold the entire set of pages needed by the application, larger page sizes can decrease, rather than improve, system performance. This results when the larger page sizes decrease the effective memory available to the process or processes running on the system, and then by increasing the latency of each individual I/O request. For example, for a process which requires one four byte data item on each page, doubling the page size while keeping the size of the memory constant halves the number of data items that the process can keep in memory simultaneously and doubles the amount of time needed to transfer the pages from secondary memory. If the transfer time dominates the amount of time needed to locate the requested page in secondary memory, the decrease in performance due to the page transfer latency may be substantial.
Thus, in paging systems, the tradeoff is often between utilization and seek times. Larger transfers reduce the number of seeks required to pull data into the local memory, and as just noted, granularity (page size) may have a dramatic effect on the storage latency and hence the time necessary to resolve page faults. Although small pages may also be used, they are implemented at the cost of poorer memory utilization and an increased number of page faults.
Systems which can access a portion of a page prior to other portions of a page are not generally known. However, systems such as the IBM RS 6000 are known which can lock portions of a page in a translation table. In addition, a system is not generally known which allows a page fault to be resolved upon partial transfer of data within the page. While similar techniques have been used to address latency issues within a hardware cache hierarchy, the present inventor knows of no such application to external memory devices and virtual memory systems.
Accordingly, it is desired to reduce storage latency so as to minimize the time necessary to resolve a page fault. Preferably, this will be accomplished by enabling the microprocessor to resolve a page fault upon partial transfer of a page. In particular, it is desired to enable the microprocessor to resume processing as soon as the critical data line which caused the page fault is received in local memory, i.e., without waiting for the remainder of the lines in the page to be transferred. It is also desired to further reduce I/O data transfer latency by sending the critical line first, i.e., by transferring the critical data line which caused the page fault before other data lines within the requested page. The present invention has been designed to meet these needs.